/*
 * Main.cpp
 *
 *  Created on: 11.10.2010
 *      Author: Luke
 */

#include <math.h>
#include "stack/Stack.h"
#include "Node.h"
#include <iostream>
#include <limits>
#include <set>
#include <cstdlib>
#include <fstream>

using namespace std;

int size = 0;

int ** points;

// tesna dolni mez
double tightLowerBound(int ** l_points){

	double minLength = numeric_limits<double>::max();
	double tightBound = 0;
	int min;

	for (int i = 0; i < size - 1; i++){


		for (int j = 0; j < size; j++){

			if (i != j) {


				if ((min = ((int)round(
						sqrt(
							pow((l_points[i][0] - l_points[j][0]),2)
							+ pow((l_points[i][1] - l_points[j][1]),2)
							) * 100
						))) < minLength ) {


					minLength = min;
				}
			}
		}

		tightBound += minLength;
	}

	return tightBound;
}


// Vytvori dvourozmerno dynamicke pole
int ** allocMatrix ( int rows, int cols )
	{
	int i;
	int ** mat;
	mat = new int * [ rows ];

	    for ( i = 0; i < rows; i ++ ) mat[i] = new int [cols];


	 return ( mat );
	}

// Uvolni pamet
	void freeMatrix ( int ** mat, int rows )
	{
	int i;

	    for ( i = 0; i < rows; i ++ ) delete [] mat[i];

	delete [] mat;
	}



// vytvori pole s body, ktere ziska ze souboru
void createPoints (){

	ifstream fileIn; // vstupni proud ze souboru (cteni)
	fileIn.open("vstup.dat", ios::in);

	int p,o;
		while(!fileIn.eof()){

			fileIn >> p >> o;
			size++;

		}

		fileIn.close();



		points = allocMatrix(size,2);


			fileIn.open("vstup.dat", ios::in);

			for (int i = 0; i < size; i++) {

			   fileIn >> points[i][0] >> points[i][1];
			}

			fileIn.close();


}

int main() {



	//int points[size][2] = {{3, 2}, {4, 5}, {1, 4}, {7, 3}, {2, 6}, {7, 7}, {5, 1}, {3, 8}};
	//int points[size][2] = {{3, 2}, {3, 4}, {4, 5}, {5, 7}, {5, 6}, {5, 5}, {3, 5}, {3, 3}};
    //int points[size][2] = {{3, 2}, {3, 8}};


	createPoints(); // nacte body ze souboru


	int path[size];


	set<int> map;

	int shortest = numeric_limits<int>::max();

	Stack * stack = new Stack();

	Node * pred = NULL;

	int numberSearch = 0;



	cout << "Tesna dolni mez: " << tightLowerBound(points) << endl;


	do{

		Node* last = NULL;

		for (int i = 0; i < size; i++){

			if (map.count(i) == 0){;
				Node * node = new Node(i, pred == NULL ? 0 : pred->getLevel() + 1,
						  pred,
						  pred == NULL ? 0 : pred->getLength() +
							(int)round(
								sqrt(
									pow((points[i][0] - points[pred->getPoint()][0]),2)
									+ pow((points[i][1] - points[pred->getPoint()][1]),2)
									) * 100
								)
							);

				numberSearch++; //Pocita kolik bylo prohledano uzlu

				if (node->getLength() < shortest){

					last = node;

					stack->push(last);
				}

			//}
			}
		}


		if (last != NULL){

			pred = last;
			map.insert(pred->getPoint()); //
		}


		if (pred->getLevel() == size - 1 || last == NULL){

			Node * node = stack->pop();

			map.erase(node->getPoint());//


			if (pred->getLength() < shortest && last != NULL) {

				shortest = pred->getLength();

				int i = size - 1;

				while (node != NULL) {

					path[i] = node->getPoint();


					cout << "|" << path[i] << "-";  // vypise nalezene reseni

					node = node->getPred();

					i--;
				}
				cout << shortest << endl; // vypise delku nalezeneho reseni

				if (shortest == tightLowerBound(points)) break; // v pripade, ze je vzdalenost rovna dolni tesne mezi, je nalezeno najratssi reseni
			}


			node = stack->pop();

			while (pred->getLevel() != node->getLevel() && !stack->isEmpty()) {

				map.erase(node->getPoint());//
				pred = node;
				node = stack->pop();
			}

			if (pred->getLevel() == node->getLevel()) {

				pred = node;
				stack->push(pred);
				map.insert(pred->getPoint()); //
			}
		}


	} while (!stack->isEmpty());

	ofstream fileOut; // vystupni proud do souboru (zapis)

	fileOut.open("vystup.dat", ios::out);

	// Vypis vyslednku algoritmu
	cout << "Nejkratsi cesta: ";
	for (int j = 0; j < size; j++){
					cout << path[j] << " ";
					fileOut << points[path[j]][0] << " " << points[path[j]][1] << endl;
				}

	fileOut.close();

	cout << " - " << shortest << endl;

	cout << "Pocet projitych uzlu: " << numberSearch << endl;









	freeMatrix(points,size); // uvolni pamet na halde

	return 0;
}
